class Solution:
    def isValid(self, s: str) -> bool:
        stk = []
        for c in s:
            if c in ['(', '[', '{']:
                stk.append(c)
            elif c in [')', ']', '}']:
                if stk == []: return False
                l = stk.pop()
                if c == ')' and l != '(': return False
                if c == ']' and l != '[': return False
                if c == '}' and l != '{': return False
        return stk == []


if __name__ == "__main__":
    soln = Solution()
    print(soln.isValid('{'))
    print(soln.isValid(')'))
    print(soln.isValid('(]'))
    print(soln.isValid('{}('))
    print(soln.isValid('([)]'))

    print(soln.isValid('()'))
    print(soln.isValid('{[]}'))
    print(soln.isValid('{}()[]'))
    print(soln.isValid('{}[([{}])[{}]]'))
